package main.java.algorithms;

import main.java.utils.SortTestHelper;

/**
 * @author Wrb
 * @date 2019/5/28 17:36
 * 从0开始索引的堆排序
 */
public class HeapSort implements Sort {
	@Override
	public void sort(int[] arr, int n) {
		for (int i = (n - 1) / 2; i >= 0; i--) {
			shiftDown(arr, n, i);
		}
		for (int i = n - 1; i > 0; i--) {
			SortTestHelper.swap(arr, 0, i);
			shiftDown(arr, i, 0);
		}
	}

	private void shiftDown(int[] arr, int n, int k) {
		while (2 * k + 1 < n) {
			int j = 2 * k + 1; //在此循环中，arr[k]和arr[j]交换位置
			if (j + 1 < n && arr[j + 1] > arr[j]) {
				j += 1;
			}
			if (arr[k] >= arr[j]) {
				break;
			}
			SortTestHelper.swap(arr, k, j);
			k = j;
		}
	}
}
